package leetcode.editor.cn;

//给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
//
// 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
//
//
// 0 <= j <= nums[i]
// i + j < n
//
//
// 返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
//
//
//
// 示例 1:
//
//
//输入: nums = [2,3,1,1,4]
//输出: 2
//解释: 跳到最后一个位置的最小跳跃数是 2。
//     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
//
//
// 示例 2:
//
//
//输入: nums = [2,3,0,1,4]
//输出: 2
//
//
//
//
// 提示:
//
//
// 1 <= nums.length <= 10⁴
// 0 <= nums[i] <= 1000
// 题目保证可以到达 nums[n-1]
//
//
// Related Topics 贪心 数组 动态规划 👍 2577 👎 0

public class JumpGameIi{
	public static void main(String[] args) {
		Solution solution = new JumpGameIi().new Solution();
		solution.jump(new int[]{2,3,1,1,4,2});

	}
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
	/**
	 * 理解
	 *
	 * @param nums
	 * @return
	 */
    public int jump(int[] nums) {
		int step=0,end=0,furthest=0;
		for(int i=0; i<nums.length-1;i++){  //这个循环终止条件很重要！
			furthest = Math.max(furthest, i+nums[i]);  //反复更新 在跳跃范围内的元素能够提供的本次即将跳跃的最远距离
			if(i==end){  //遍历到上个起跳点能到的最远距离
				end = furthest;  //end更新为：右边界为i时候能提供的最远距离
				step++;  //先把步数+1，但实际还没跳（这也解释了循环终止条件）
			}
		}
		return step;


    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
